package 代码随想录_回溯.力扣_回溯.岛屿系列;

/**
 * 岛屿系列问题看本题的题解：讲的很棒！
 * https://leetcode.cn/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/
 * @author zx
 * @create 2022-08-12 21:16
 */
public class 岛屿数量_200 {
    public int numIslands(char[][] grid) {
        int res = 0;
        for(int i = 0;i < grid.length;i++){
            for(int j = 0;j < grid[0].length;j++){
                if(grid[i][j] == '1'){
                    dfs(grid,i,j);
                    res++;
                }
            }
        }
        return res;
    }
    /**
     * 如何避免重复遍历
     * 每走过一个陆地格子,就把格子的值改为2,当遇到2的时候,就知道这是遍历过的格子
     * 0 —— 海洋格子
     * 1 —— 陆地格子(未遍历过)
     * 2 —— 陆地格子(已遍历过)
     */
    private void dfs(char[][] grid, int i, int j){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length){
            return;
        }
        if(grid[i][j] != '1'){
            return;
        }
        grid[i][j] = '2';
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}
